package com.game.astar;

import com.game.astar.mode.DirectionEnum;
import com.game.astar.util.SceneConfig;

/**
 * 二叉堆寻路驱动
 * @author 庄宏晓
 * @date 2013-6-17
 */
public class FindingHeapDrive
{
	int ID = 1;
	
	/**
	 * 地图数据
	 */
	char[][] codeData;
	
	/**
	 * 节点ID列表
	 */
	int[] idArr;
	
	/**
	 * 坐标x列表
	 */
	int[] xArr;
	
	/**
	 * 坐标y列表
	 */
	int[] yArr;
	
	/**
	 * f评估值列表
	 */
	int[] fArr;
	
	/**
	 * 记录堆中的元素数量
	 */
	int size = 0;
	
	/**
	 * 寻路
	 * @param startX	开始坐标x
	 * @param startY	开始坐标y
	 * @param endX		终点坐标x
	 * @param endY		终点坐标y
	 * @return			是否寻到路径
	 * @create 2013-6-17 庄宏晓
	 */
	public boolean searchPath(int startX, int startY, int endX, int endY)
	{
		/*地点异常*/
		if(codeData[startY][startX] == SceneConfig.STOPCHAR || codeData[endY][endX] == SceneConfig.STOPCHAR)
		{
			return Boolean.FALSE;
		}
		
		/*添加起始点*/
		addNode(startX, startY, getH(startX, startY, endX, endY));
		
		boolean bool = search(endX, endY);
		
		if(bool)
		{
			/*设置路径*/
			
		}
		
		return bool;
	}
	
	private boolean search(int endX, int endY) 
	{
		while(size > 0)
		{
			if(xArr[idArr[0]] == endX && yArr[idArr[0]] == endY)
			{
				return Boolean.TRUE;
			}
			
			/* 添加8方向子节点 */
			addChild(DirectionEnum.UP, 1, endX, endY);
			addChild(DirectionEnum.DOWN, 1, endX, endY);
			addChild(DirectionEnum.LEFT, 1, endX, endY);
			addChild(DirectionEnum.RIGHT, 1, endX, endY);
			addChild(DirectionEnum.LEFT_UP, 1, endX, endY);
			addChild(DirectionEnum.LEFT_DOWN, 1, endX, endY);
			addChild(DirectionEnum.RIGHT_UP, 1, endX, endY);
			addChild(DirectionEnum.RIGHT_DOWN, 1, endX, endY);
		}
		
		return Boolean.FALSE;
	}

	/**
	 * 添加一个子节点
	 * @param direction	方向
	 * @param index		位置
	 * @param endX		终点坐标x
	 * @param endY		终点坐标y
	 * @create 2013-6-17 庄宏晓
	 */
	void addChild(DirectionEnum direction, int index, int endX, int endY)
	{
		/*获得坐标x*/
		int x = xArr[index] + direction.getX();
		/*获得坐标y*/
		int y = yArr[index] + direction.getY();
		
		/*坐标异常*/
		if(x < 0 || y < 0 || y >= codeData.length || x >= codeData[endY].length - 1 || codeData[y][x] == SceneConfig.STOPCHAR)
		{
			return;
		}
		
		/*计算评估值f*/
		int f = getH(x, y, endX, endY) + direction.getG();
		
		/*添加子节点*/
		addNode(xArr[index] + direction.getX(), xArr[index] + direction.getX(), f);
		
		/*子节点位置*/
		int childIndex = size;
		
		/*获取父节点*/
		int superIndex = childIndex / 8;
		
		/* 规则插入 */
		while(fArr[childIndex] < fArr[superIndex])
		{
			changeIndex(index, superIndex);
			
			/*子节点位置更新*/
			childIndex = superIndex;
			superIndex = childIndex / 8;
		}
		
		this.size --;
		
		int index_ = childIndex + 1;
		
		while(index_ <= size)
		{
			if(fArr[childIndex] > fArr[index_])
			{
				changeIndex(childIndex, index_);
				index_ = childIndex + 1;
			}
		}
	}
	
	/**
	 * 获取h值
	 * @param x	当前坐标x
	 * @param y	当前坐标y
	 * @param endX	终点坐标x
	 * @param endY	终点坐标y
	 * @return		h值
	 * @create 2013-6-17 庄宏晓
	 */
	int getH(int x, int y, int endX, int endY)
	{
		return (Math.abs(endX - x) + Math.abs(endY - y)) * 10;
	}
	
	/**
	 * 加入一个节点
	 * @param x	坐标x
	 * @param y	坐标y
	 * @param f	评估值
	 * @create 2013-6-17 庄宏晓
	 */
	boolean addNode(int x, int y, int f)
	{
		int id = x << 2 + y;
		
		this.idArr[++size] = id;
		this.xArr[id] = x;
		this.yArr[id] = y;
		this.fArr[id] = f;
		
		return Boolean.TRUE;
	}
	
	void removeNode()
	{
		this.idArr[1] = this.idArr[size];
//		this.idArr[size] = 0;
		
		this.xArr[1] = this.xArr[size];
//		this.xArr[size] = 0;
		
		this.yArr[1] = this.yArr[size];
//		this.yArr[size] = 0;
		
		this.fArr[1] = this.fArr[size];
//		this.fArr[size] = 0;
		
		this.size--;
	}
	
	/**
	 * 改变中位置
	 * @param arr		数组
	 * @param index1	位置1
	 * @param index2	位置2
	 * @create 2013-6-17 庄宏晓
	 */
	private void changeIndex(int index1, int index2)
	{
		idArr[index1] = idArr[index1] + idArr[index2];
		idArr[index2] = idArr[index1] - idArr[index2];
		idArr[index1] = idArr[index1] - idArr[index2];
	}
	
	public FindingHeapDrive(char[][] codeData)
	{
		this.codeData = codeData;
		idArr = new int[codeData.length * codeData[0].length + 1];
		xArr = new int[codeData.length * codeData[0].length + 1];
		yArr = new int[codeData.length * codeData[0].length + 1];
		fArr = new int[codeData.length * codeData[0].length + 1];
	}
}
